package L622;

import java.util.Map;

/**
 * @program: javase
 * @description: 判断后序遍历序列是否二叉排序树
 * @author: luolidong
 * @create: 2021-06-22 11:08
 * @version: 1.0
 */
public class VerifyPostOrder {
    public boolean verifyPostorder(int[] postorder) {
        return verify(postorder, 0, postorder.length-1);
    }
    public boolean verify(int[] postorder,int left,int right){
        //左右指针相遇，表示符合要求
        if(left>=right) return true;
        //
        int mid=left;
        while (postorder[mid]<postorder[right]){
            mid++;
        }
        //mid到right之间的一定要比right大
        int r=mid;
        while (r<right){
            if(postorder[r]<postorder[right]) return false;
            r++;
        }
        return verify(postorder, left, mid-1)&&verify(postorder, mid, right-1);
    }

    public static void main(String[] args) {
        boolean b = new VerifyPostOrder().verifyPostorder(new int[]{1, 3, 2, 4, 8,6,9, 5});
        System.out.println(b);
    }
}
